﻿namespace Leetcode.N0051;
public class Solution
{
    public IList<IList<string>> SolveNQueens(int n)
    {

        var leftLine = new bool[n * 2 - 1];
        var rightLine = new bool[leftLine.Length];
        var verticalLine = new bool[n];

        var ans = new List<int[]>();
        for (int col = 0; col < n; col++)
        {
            var s = new int[n];
            this.SolveNQueens(0, col, leftLine, rightLine, verticalLine, s, ans);
        }

        return ans.Select(i => i.Select(j =>
        {
            var c = new char[n];
            for (int k = 0; k < n; k++)
            {
                c[k] = j == k ? 'Q' : '.';
            }
            return new string(c);
        }).ToArray()).ToArray();
    }

    private void SolveNQueens(int row, int col, bool[] leftLine, bool[] rightLine, bool[] verticalLine, int[] s, IList<int[]> ans)
    {
        var n = verticalLine.Length;
        var leftLineIndex = n + (row - col) - 1;
        var rightLineIndex = row + col;


        if (verticalLine[col] || leftLine[leftLineIndex] || rightLine[rightLineIndex])
        {
            return;
        }

        s[row] = col;
        if (row == n - 1)
        {
            var r = new int[s.Length];
            s.CopyTo(r, 0);
            ans.Add(r);
            return;
        }

        verticalLine[col] = true;
        leftLine[leftLineIndex] = true;
        rightLine[rightLineIndex] = true;

        for (int i = 0; i < n; i++)
        {
            this.SolveNQueens(row + 1, i, leftLine, rightLine, verticalLine, s, ans);
        }

        verticalLine[col] = false;
        leftLine[leftLineIndex] = false;
        rightLine[rightLineIndex] = false;
    }

}